package com.fr.lintcode;

import java.util.Arrays;
import java.util.Comparator;

import org.junit.Test;

/**
*作者：furong
*日期：2017年1月11日
*时间：下午4:46:07
*/
public class Q184 {
    /**
     *@param num: A list of non negative integers
     *@return: A string
     */
    public String largestNumber(int[] num) {
        if (num == null || num.length == 0) {
            return "";
        }
        int length = num.length;
        String[] s = new String[length];
        for (int i = 0; i < length; i++) {
            s[i] = String.valueOf(num[i]);
        }
        Arrays.sort(s, new c());
        String rs = "";
        for (int i = 0; i < length; i++) {
            rs += s[i];
        }
        java.util.regex.Pattern pattern = java.util.regex.Pattern.compile("0+");
        if (pattern.matcher(rs).matches()) {
            return "0";
        }
        return rs;
    }

    class c implements Comparator<String> {

        @Override
        public int compare(String o1, String o2) {
            int l1 = o1.length();
            int l2 = o2.length();
            int limit = Math.min(l1, l2);
            for (int i = 0; i < limit; i++) {
                char c1 = o1.charAt(i);
                char c2 = o2.charAt(i);
                if (c1 > c2) {
                    return -1;
                } else if (c1 < c2) {
                    return 1;
                }
            }
            if (l1 > l2) {
                char c2 = o2.charAt(limit - 1);
                for (int i = limit; i < l1; i++) {
                    char c1 = o1.charAt(i);
                    if (c1 > c2) {
                        return -1;
                    } else if (c1 < c2) {
                        return 1;
                    }
                }
            } else if (l1 < l2) {
                char c1 = o1.charAt(limit - 1);
                char c2;
                for (int i = limit; i < l2; i++) {
                    c2 = o2.charAt(i);
                    if (c1 > c2) {
                        return -1;
                    } else if (c1 < c2) {
                        return 1;
                    }
                }
            }
            return 0;
        }
    }

    @Test
    public void testA() {
        int[] num = { 7, 778, 7, 776 };
        System.out.println(largestNumber(num));
    }
}
